package concurrency.part1.task2.sorts;


import java.util.Arrays;

public class MergeSort {
    static class Pair{
        int a[];
        int b[];

        Pair(int[] a, int[] b) {
            this.a = a;
            this.b = b;
        }
    }

    public static int[] sort(int a[]) {
        if (a.length<2)
            return a;
        Pair p=split(a);
        return merge(sort(p.a),sort(p.b));
    }

    static int[] merge(int[] a, int[] b) {
        int res[]=new int[a.length+b.length],currA=0,currB=0,currRes=0;
        while (currA<a.length && currB<b.length){
            if (a[currA]<b[currB])
                res[currRes++]=a[currA++];
            else res[currRes++]=b[currB++];
        }
        currRes=addToEnd(res,currRes,a,currA);
        addToEnd(res,currRes,b,currB);
        return res;
    }

    private static int addToEnd(int r[],int currR,int a[],int currA) {
        while (currA<a.length) r[currR++]=a[currA++];
        return currR;
    }

    static Pair split(int[] a) {
        int m=a.length>>1;
        return new Pair(Arrays.copyOfRange(a,0,m)
                ,Arrays.copyOfRange(a,m,a.length));
    }
}
